package parser;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import controlFlowGraph.BinaryOp;
import controlFlowGraph.CFG;
import controlFlowGraph.CFGEdge;
import controlFlowGraph.CFGLabel;
import controlFlowGraph.CFGNode;
import controlFlowGraph.Constant;
import controlFlowGraph.Expression;
import controlFlowGraph.LabAssign;
import controlFlowGraph.LabLoad;
import controlFlowGraph.LabNeg;
import controlFlowGraph.LabNop;
import controlFlowGraph.LabPos;
import controlFlowGraph.LabStore;
import controlFlowGraph.UnaryOp;
import controlFlowGraph.Variable;

import config.*;

public class Parser {

	/**
	 * Lists the whole program in linear Order
	 */
	private List<Token> TokenList = new ArrayList<Token>();
	/**
	 * Index for the position of the current Token in TokenList
	 */
	private int pointer;
	/**
	 * Map that remembers if there is a node for a id, and book-keeps the node
	 */
	private Map<Integer,CFGNode> nodeMapping = new HashMap<Integer,CFGNode>();
	
	/**
	 * Constructor for a parser. It takes a lexer that provides
	 * an iterator over all Tokens. If the Source-File is empty , a
	 * ParserException is thrown.
	 * 
	 * @param lexer
	 *            the lexer, provides token stream
	 * @throws ParserException
	 */
	public Parser(Lexer lexer) throws ParserException {
		this.pointer = 0;
		if (lexer.hasNext()) {
			this.TokenList = lexer.getTokenList();
		} else {
			throw new ParserException("Sourcecode-File is empty");
		}
	}

	/**
	 * Returns true, if the current Token has one of the given TokenType
	 * 
	 * @param tokenTypes
	 *            the expected TokenTypes
	 * @return true, if the current Token has one of the given TokenTypes
	 */
	protected boolean peek(TokenType... tokenTypes) {
		for (TokenType t : tokenTypes) {
			if (this.TokenList.get(this.pointer).getType().equals(t))
				return true;
		}
		return false;
	}

	/**
	 * Returns the current Token, if it has one of the given TokenTypes. The
	 * current Token is updated. Otherwise a ParserException is thrown
	 * 
	 * @param tokenTypes
	 * @return the current token
	 * @throws ParserException
	 */
	protected Token accept(TokenType... tokenTypes) throws ParserException {
		if (peek(tokenTypes)) {
			Token res = this.TokenList.get(this.pointer);
			pointer = pointer + 1;
			if (pointer > this.TokenList.size()) {
				throw new ParserException("Reached end of File with errors.");
			}
			return res;
		}
		throw new ParserException(this.TokenList.get(pointer) + "expected : " + tokenTypes);
	}

	/**
	 * Parse function
	 * 
	 * @return a CFG
	 * @throws ParserException
	 */
	public CFG parse() throws ParserException {
		if (peek(TokenType.EOF))
			throw new ParserException("Analysis File is empty!");
		
		// parse analysis
		accept(TokenType.ANALYSIS);
		if (peek(TokenType.AVAILEXPR)) {
			GlobalConfig.analysisType = AnalysisTypes.AvailableExpressions;
			accept(TokenType.AVAILEXPR);
		} else if (peek(TokenType.TRULYLIVE)){
			GlobalConfig.analysisType = AnalysisTypes.TrulyLiveVariables;
			accept(TokenType.TRULYLIVE);
		} else {
			accept(TokenType.INTERVAL);
			GlobalConfig.analysisType = AnalysisTypes.IntervalAnalysis;
		}
		
		// parse algorithm
		accept(TokenType.ALGORITHM);
		if (peek(TokenType.WORKLIST)) {
			GlobalConfig.algorithm = FixpointAlgorithms.WORKLIST;
			accept(TokenType.WORKLIST);
		} else if (peek(TokenType.RROBIN)) {
			GlobalConfig.algorithm = FixpointAlgorithms.ROUNDROBIN;
			accept(TokenType.RROBIN);
		} else {
			accept(TokenType.RECURSIVE);
			GlobalConfig.algorithm = FixpointAlgorithms.RECURSIVE;
		}
		
		// parse output format
		accept(TokenType.OUTPUT);
		if (peek(TokenType.OUTANA)) {
			GlobalConfig.outputFormat = OutputFormat.ANALYSIS;
			accept(TokenType.OUTANA);
		} else {
			accept(TokenType.OUTTRANS);
			GlobalConfig.outputFormat = OutputFormat.TRANSFORMATION;
		}
		
		// parse Program
		accept(TokenType.PROGRAM);
		while (!peek(TokenType.EOF)) {
			CFGNode from = parseCfgNode();
			CFGLabel lab = parseLabel();
			CFGNode to = parseCfgNode();
			CFGEdge edge = new CFGEdge(from, to, lab);
			from.addOutEdge(edge);
			to.addInEdge(edge);
		}
		if (GlobalConfig.debug) {
			System.out.println("We have " + this.nodeMapping.size() + " different nodes!");
		}
		Set<CFGNode> allNodes = new HashSet<CFGNode>();
		Collection<CFGNode> nod = this.nodeMapping.values();
		for (CFGNode n : nod) {
			allNodes.add(n);
		}
		return new CFG(allNodes, this.nodeMapping.get(0), this.nodeMapping.get(-1));
	}
	
	private CFGLabel parseLabel() throws ParserException {
		if (peek(TokenType.SEMI)) {
			accept(TokenType.SEMI);
			return new LabNop();
		}
		if (peek(TokenType.POS)) {
			accept(TokenType.POS);
			accept(TokenType.LPAREN);
			Expression exp = parseExpression();
			accept(TokenType.RPAREN);
			if (peek(TokenType.SEMI)) {
				accept(TokenType.SEMI);
			}
			return new LabPos(exp);
		}
		if (peek(TokenType.NEG)) {
			accept(TokenType.NEG);
			accept(TokenType.LPAREN);
			Expression exp = parseExpression();
			accept(TokenType.RPAREN);
			if (peek(TokenType.SEMI)) {
				accept(TokenType.SEMI);
			}
			return new LabNeg(exp);
		}
		if (peek(TokenType.MEMORY)) {
			accept(TokenType.MEMORY);
			accept(TokenType.LSQUARE);
			Expression e1 = parseExpression();
			accept(TokenType.RSQUARE);
			accept(TokenType.ASSIGN);
			Expression e2 = parseExpression();
			accept(TokenType.SEMI);
			return new LabStore(e1, e2);
		}
		Variable x = parseVariable();
		accept(TokenType.ASSIGN);
		if (peek(TokenType.MEMORY)) {
			accept(TokenType.MEMORY);
			accept(TokenType.LSQUARE);
			Expression e = parseExpression();
			accept(TokenType.RSQUARE);
			accept(TokenType.SEMI);
			return new LabLoad(x, e);
		}
		Expression e = parseExpression();
		accept(TokenType.SEMI);
		return new LabAssign(x, e);
	}
	
	private Variable parseVariable() throws ParserException {
		Token tok = accept(TokenType.IDENT);
		Variable res = new Variable(tok.getText());
		GlobalConfig.variableSet.add(res);
		return res;
	}

	private Constant parseConstant() throws ParserException {
		Token tok = accept(TokenType.INT_LITERAL);
		return new Constant(Integer.parseInt(tok.getText()));
	}
	
	private Expression parseAtom() throws ParserException {
		if (peek(TokenType.IDENT)) {
			return parseVariable();
		}
		return parseConstant();
	}
	
	private Expression parseExpression() throws ParserException {
		// Unary
		if (peek(TokenType.PLUS,TokenType.MINUS)) {
			Token tok = accept(TokenType.PLUS,TokenType.MINUS);
			Expression exp = parseAtom();
			Expression res = new UnaryOp(exp, tok);
			GlobalConfig.expressionSet.add(res);
			return res;
		}
		// ATOM or binary
		Expression lop = parseAtom();
		if (peek(TokenType.PLUS, TokenType.MINUS, TokenType.MUL, TokenType.DIVORSLASH,
				TokenType.LT, TokenType.GT, TokenType.LE, TokenType.GE,
				TokenType.EQ, TokenType.NE)) {
			Token tok = accept(TokenType.PLUS, TokenType.MINUS, TokenType.MUL, TokenType.DIVORSLASH,
					TokenType.LT, TokenType.GT, TokenType.LE, TokenType.GE,
					TokenType.EQ, TokenType.NE);
			Expression rop = parseAtom();
			Expression res = new BinaryOp(tok, lop, rop);
			GlobalConfig.expressionSet.add(res);
			return res;
		}
		GlobalConfig.expressionSet.add(lop);
		return lop;
	}
	
	private CFGNode parseCfgNode() throws ParserException {
		if (peek(TokenType.START)) {
			accept(TokenType.START);
			if (nodeMapping.containsKey(0)) {
				return nodeMapping.get(0);
			}
			CFGNode res = new CFGNode(0);
			nodeMapping.put(0, res);
			return res;
		}
		if (peek(TokenType.END)) {
			accept(TokenType.END);
			if (nodeMapping.containsKey(-1)) {
				return nodeMapping.get(-1);
			}
			CFGNode res = new CFGNode(-1);
			nodeMapping.put(-1, res);
			return res;
		}
		Token tok = accept(TokenType.IDENT);
		String text = tok.getText();
		if (!text.startsWith("P")) {
			System.out.println("Illegal Node: must start with P or start or end!");
			return null;
		}
		else {
			int id = Integer.parseInt(text.substring(1));
			if (nodeMapping.containsKey(id)) {
				return nodeMapping.get(id);
			}
			CFGNode res = new CFGNode(id);
			nodeMapping.put(id, res);
			return res;
		}
	}
}
// end parser